<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>数组-链表-栈-队列-cnblog | 凌歆的博客</title>
    <meta name="generator" content="VuePress 1.9.5">
    <link rel="icon" href="/img/favicon.ico">
    <meta name="description" content="web前端技术博客,专注web前端学习与总结。JavaScript,js,ES6,TypeScript,vue,React,python,css3,html5,Node,git,github等技术文章。">
    <meta name="keywords" content="前端博客,个人技术博客,前端,前端开发,前端框架,web前端,前端面试题,技术文档,学习,面试,JavaScript,js,ES6,TypeScript,vue,python,css3,html5,Node,git,github,markdown">
    <meta name="baidu-site-verification" content="7F55weZDDc">
    <meta name="theme-color" content="#11a8cd">
    
    <link rel="preload" href="/assets/css/0.styles.d9c8cf8c.css" as="style"><link rel="preload" href="/assets/js/app.57550e13.js" as="script"><link rel="preload" href="/assets/js/2.f014c35f.js" as="script"><link rel="preload" href="/assets/js/99.07dc87d8.js" as="script"><link rel="prefetch" href="/assets/js/10.03a98811.js"><link rel="prefetch" href="/assets/js/100.145e708e.js"><link rel="prefetch" href="/assets/js/101.098ca5c8.js"><link rel="prefetch" href="/assets/js/102.4d45c69a.js"><link rel="prefetch" href="/assets/js/103.499de505.js"><link rel="prefetch" href="/assets/js/104.c2c1b9b6.js"><link rel="prefetch" href="/assets/js/105.4e9b0663.js"><link rel="prefetch" href="/assets/js/106.9bb8cf6f.js"><link rel="prefetch" href="/assets/js/107.a81b32d7.js"><link rel="prefetch" href="/assets/js/108.81511e67.js"><link rel="prefetch" href="/assets/js/109.6a6741bf.js"><link rel="prefetch" href="/assets/js/11.e8729182.js"><link rel="prefetch" href="/assets/js/110.de657fe7.js"><link rel="prefetch" href="/assets/js/111.b092af6d.js"><link rel="prefetch" href="/assets/js/112.2dca5709.js"><link rel="prefetch" href="/assets/js/113.dbed1fac.js"><link rel="prefetch" href="/assets/js/114.e95a0131.js"><link rel="prefetch" href="/assets/js/115.2e3e8285.js"><link rel="prefetch" href="/assets/js/116.e64f7fec.js"><link rel="prefetch" href="/assets/js/117.583552c9.js"><link rel="prefetch" href="/assets/js/118.aa5d18f0.js"><link rel="prefetch" href="/assets/js/119.0c7b52d7.js"><link rel="prefetch" href="/assets/js/12.d63acec2.js"><link rel="prefetch" href="/assets/js/120.13f86281.js"><link rel="prefetch" href="/assets/js/121.e2b5b7f9.js"><link rel="prefetch" href="/assets/js/122.5252216a.js"><link rel="prefetch" href="/assets/js/123.8b8a3503.js"><link rel="prefetch" href="/assets/js/124.60df855c.js"><link rel="prefetch" href="/assets/js/125.f073ab1c.js"><link rel="prefetch" href="/assets/js/126.7b73de6a.js"><link rel="prefetch" href="/assets/js/127.4e25971c.js"><link rel="prefetch" href="/assets/js/128.0edf0e06.js"><link rel="prefetch" href="/assets/js/129.5cb5a70a.js"><link rel="prefetch" href="/assets/js/13.2259ef71.js"><link rel="prefetch" href="/assets/js/130.00247fda.js"><link rel="prefetch" href="/assets/js/131.d6fc003a.js"><link rel="prefetch" href="/assets/js/132.1a32b18f.js"><link rel="prefetch" href="/assets/js/133.e46c0193.js"><link rel="prefetch" href="/assets/js/134.a6ad681f.js"><link rel="prefetch" href="/assets/js/135.2fcbe137.js"><link rel="prefetch" href="/assets/js/136.f69bf451.js"><link rel="prefetch" href="/assets/js/137.b9ef2fcc.js"><link rel="prefetch" href="/assets/js/138.7fdd9feb.js"><link rel="prefetch" href="/assets/js/139.a3a37c91.js"><link rel="prefetch" href="/assets/js/14.0d6b23b9.js"><link rel="prefetch" href="/assets/js/140.a7c013ae.js"><link rel="prefetch" href="/assets/js/141.956c36ce.js"><link rel="prefetch" href="/assets/js/142.5aacfe42.js"><link rel="prefetch" href="/assets/js/143.57d691ef.js"><link rel="prefetch" href="/assets/js/144.b1e5766e.js"><link rel="prefetch" href="/assets/js/145.463284b7.js"><link rel="prefetch" href="/assets/js/146.6cc6420c.js"><link rel="prefetch" href="/assets/js/147.5b78c5a2.js"><link rel="prefetch" href="/assets/js/148.8d1d7679.js"><link rel="prefetch" href="/assets/js/149.4e0eb213.js"><link rel="prefetch" href="/assets/js/15.f6fde69d.js"><link rel="prefetch" href="/assets/js/150.b183de37.js"><link rel="prefetch" href="/assets/js/151.729ae770.js"><link rel="prefetch" href="/assets/js/152.b1297018.js"><link rel="prefetch" href="/assets/js/153.bb991bca.js"><link rel="prefetch" href="/assets/js/154.6f2286aa.js"><link rel="prefetch" href="/assets/js/155.6a9c7e4d.js"><link rel="prefetch" href="/assets/js/156.f7bd535d.js"><link rel="prefetch" href="/assets/js/157.64c0065c.js"><link rel="prefetch" href="/assets/js/158.d31ae949.js"><link rel="prefetch" href="/assets/js/159.7daea8a7.js"><link rel="prefetch" href="/assets/js/16.7be21beb.js"><link rel="prefetch" href="/assets/js/160.33cc971a.js"><link rel="prefetch" href="/assets/js/161.1676442a.js"><link rel="prefetch" href="/assets/js/162.71378046.js"><link rel="prefetch" href="/assets/js/163.99e49959.js"><link rel="prefetch" href="/assets/js/164.306f07d2.js"><link rel="prefetch" href="/assets/js/165.170977c7.js"><link rel="prefetch" href="/assets/js/166.f8602525.js"><link rel="prefetch" href="/assets/js/167.eea5c001.js"><link rel="prefetch" href="/assets/js/168.0146a311.js"><link rel="prefetch" href="/assets/js/169.05f9c9d9.js"><link rel="prefetch" href="/assets/js/17.2543f471.js"><link rel="prefetch" href="/assets/js/170.25d602b2.js"><link rel="prefetch" href="/assets/js/171.1ada26a6.js"><link rel="prefetch" href="/assets/js/172.2a0f697c.js"><link rel="prefetch" href="/assets/js/173.230d8ca8.js"><link rel="prefetch" href="/assets/js/174.e3758a2b.js"><link rel="prefetch" href="/assets/js/175.0f19f8ea.js"><link rel="prefetch" href="/assets/js/176.bf70d37d.js"><link rel="prefetch" href="/assets/js/177.4400f272.js"><link rel="prefetch" href="/assets/js/178.85af7b89.js"><link rel="prefetch" href="/assets/js/179.4cfaaaa2.js"><link rel="prefetch" href="/assets/js/18.394415f8.js"><link rel="prefetch" href="/assets/js/180.449c8409.js"><link rel="prefetch" href="/assets/js/181.73276924.js"><link rel="prefetch" href="/assets/js/182.5fab25cc.js"><link rel="prefetch" href="/assets/js/183.ecd4934d.js"><link rel="prefetch" href="/assets/js/184.246092cf.js"><link rel="prefetch" href="/assets/js/185.c671cd86.js"><link rel="prefetch" href="/assets/js/186.49bd1963.js"><link rel="prefetch" href="/assets/js/187.1fb32764.js"><link rel="prefetch" href="/assets/js/188.7c6885e9.js"><link rel="prefetch" href="/assets/js/189.a8701dec.js"><link rel="prefetch" href="/assets/js/19.ca7db8ea.js"><link rel="prefetch" href="/assets/js/190.ae3d3bde.js"><link rel="prefetch" href="/assets/js/191.ad7cd44e.js"><link rel="prefetch" href="/assets/js/192.bc443842.js"><link rel="prefetch" href="/assets/js/193.e4755764.js"><link rel="prefetch" href="/assets/js/194.814112ce.js"><link rel="prefetch" href="/assets/js/195.1c0aaa80.js"><link rel="prefetch" href="/assets/js/196.a6bd7add.js"><link rel="prefetch" href="/assets/js/20.4e91cd31.js"><link rel="prefetch" href="/assets/js/21.f095e6e1.js"><link rel="prefetch" href="/assets/js/22.72f4b8ab.js"><link rel="prefetch" href="/assets/js/23.e94eb9d2.js"><link rel="prefetch" href="/assets/js/24.0eae7d6f.js"><link rel="prefetch" href="/assets/js/25.36157609.js"><link rel="prefetch" href="/assets/js/26.dc5b6cba.js"><link rel="prefetch" href="/assets/js/27.c19b7b63.js"><link rel="prefetch" href="/assets/js/28.3aceae59.js"><link rel="prefetch" href="/assets/js/29.536091b3.js"><link rel="prefetch" href="/assets/js/3.d11119c4.js"><link rel="prefetch" href="/assets/js/30.821a4a30.js"><link rel="prefetch" href="/assets/js/31.5238784c.js"><link rel="prefetch" href="/assets/js/32.10bc7179.js"><link rel="prefetch" href="/assets/js/33.c1ed69c9.js"><link rel="prefetch" href="/assets/js/34.8d384231.js"><link rel="prefetch" href="/assets/js/35.d8890e52.js"><link rel="prefetch" href="/assets/js/36.eca37ad5.js"><link rel="prefetch" href="/assets/js/37.802549e3.js"><link rel="prefetch" href="/assets/js/38.53841770.js"><link rel="prefetch" href="/assets/js/39.7ae44409.js"><link rel="prefetch" href="/assets/js/4.493b9bca.js"><link rel="prefetch" href="/assets/js/40.ce56364a.js"><link rel="prefetch" href="/assets/js/41.85f0114b.js"><link rel="prefetch" href="/assets/js/42.714da6e2.js"><link rel="prefetch" href="/assets/js/43.fee4437c.js"><link rel="prefetch" href="/assets/js/44.b039b68b.js"><link rel="prefetch" href="/assets/js/45.96a55605.js"><link rel="prefetch" href="/assets/js/46.956ffb03.js"><link rel="prefetch" href="/assets/js/47.147d9218.js"><link rel="prefetch" href="/assets/js/48.ff787b40.js"><link rel="prefetch" href="/assets/js/49.871eee87.js"><link rel="prefetch" href="/assets/js/5.e0ba07d7.js"><link rel="prefetch" href="/assets/js/50.99b7c29e.js"><link rel="prefetch" href="/assets/js/51.8ecbf4ba.js"><link rel="prefetch" href="/assets/js/52.53d91d7e.js"><link rel="prefetch" href="/assets/js/53.af8a0d2a.js"><link rel="prefetch" href="/assets/js/54.a2f848b5.js"><link rel="prefetch" href="/assets/js/55.267e9947.js"><link rel="prefetch" href="/assets/js/56.0b201c40.js"><link rel="prefetch" href="/assets/js/57.cbdfd6f7.js"><link rel="prefetch" href="/assets/js/58.636c0c3f.js"><link rel="prefetch" href="/assets/js/59.fc9216c4.js"><link rel="prefetch" href="/assets/js/6.b98373f2.js"><link rel="prefetch" href="/assets/js/60.34f16fc4.js"><link rel="prefetch" href="/assets/js/61.4d130bd8.js"><link rel="prefetch" href="/assets/js/62.927caa10.js"><link rel="prefetch" href="/assets/js/63.a451fee0.js"><link rel="prefetch" href="/assets/js/64.32a5d47b.js"><link rel="prefetch" href="/assets/js/65.bc099429.js"><link rel="prefetch" href="/assets/js/66.3953050d.js"><link rel="prefetch" href="/assets/js/67.e934823b.js"><link rel="prefetch" href="/assets/js/68.4bcb52b0.js"><link rel="prefetch" href="/assets/js/69.bede18c8.js"><link rel="prefetch" href="/assets/js/7.8de8df2d.js"><link rel="prefetch" href="/assets/js/70.fce1daac.js"><link rel="prefetch" href="/assets/js/71.ea0a8c5d.js"><link rel="prefetch" href="/assets/js/72.15382c9e.js"><link rel="prefetch" href="/assets/js/73.848364d3.js"><link rel="prefetch" href="/assets/js/74.5fd08a50.js"><link rel="prefetch" href="/assets/js/75.c937c70d.js"><link rel="prefetch" href="/assets/js/76.a0dacd5a.js"><link rel="prefetch" href="/assets/js/77.4019cc23.js"><link rel="prefetch" href="/assets/js/78.9676a9e1.js"><link rel="prefetch" href="/assets/js/79.e46e10d5.js"><link rel="prefetch" href="/assets/js/8.2098eb96.js"><link rel="prefetch" href="/assets/js/80.987e83cb.js"><link rel="prefetch" href="/assets/js/81.eb98ff36.js"><link rel="prefetch" href="/assets/js/82.623561a7.js"><link rel="prefetch" href="/assets/js/83.e256d909.js"><link rel="prefetch" href="/assets/js/84.7d06a550.js"><link rel="prefetch" href="/assets/js/85.b8d9879e.js"><link rel="prefetch" href="/assets/js/86.31c4581b.js"><link rel="prefetch" href="/assets/js/87.e06ee05e.js"><link rel="prefetch" href="/assets/js/88.81ef718d.js"><link rel="prefetch" href="/assets/js/89.ba237d2f.js"><link rel="prefetch" href="/assets/js/9.36092fd0.js"><link rel="prefetch" href="/assets/js/90.ad2c9d92.js"><link rel="prefetch" href="/assets/js/91.a661f52d.js"><link rel="prefetch" href="/assets/js/92.1c28035b.js"><link rel="prefetch" href="/assets/js/93.c8b8e3d6.js"><link rel="prefetch" href="/assets/js/94.b6bc4a44.js"><link rel="prefetch" href="/assets/js/95.92cea882.js"><link rel="prefetch" href="/assets/js/96.5373491b.js"><link rel="prefetch" href="/assets/js/97.bb39efc8.js"><link rel="prefetch" href="/assets/js/98.af7a030f.js">
    <link rel="stylesheet" href="/assets/css/0.styles.d9c8cf8c.css">
  </head>
  <body class="theme-mode-light">
    <div id="app" data-server-rendered="true"><div class="theme-container sidebar-open have-rightmenu"><header class="navbar blur"><div title="目录" class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><img src="https://lingxin-tanhua.oss-cn-shanghai.aliyuncs.com/QQ%E6%88%AA%E5%9B%BE20220503092755.png" alt="凌歆的博客" class="logo"> <span class="site-name can-hide">凌歆的博客</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端" class="dropdown-title"><a href="/web/" class="link-title">前端</a> <span class="title" style="display:none;">前端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>学习笔记</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/note/html/" class="nav-link">HTML笔记</a></li><li class="dropdown-subitem"><a href="/note/js-low/" class="nav-link">JavaScript基础笔记</a></li><li class="dropdown-subitem"><a href="/note/js-high/" class="nav-link">JavaScript高阶笔记</a></li><li class="dropdown-subitem"><a href="/note/js-dom-bom/" class="nav-link">JavaScript DOM和BOM笔记</a></li><li class="dropdown-subitem"><a href="/note/jquery/" class="nav-link">jQuery笔记</a></li><li class="dropdown-subitem"><a href="/note/ajax/" class="nav-link">Ajax笔记</a></li><li class="dropdown-subitem"><a href="/note/nodejs/" class="nav-link">NodeJs笔记</a></li><li class="dropdown-subitem"><a href="/note/reg/" class="nav-link">正则表达式笔记</a></li><li class="dropdown-subitem"><a href="/note/vue/" class="nav-link">Vue笔记</a></li><li class="dropdown-subitem"><a href="/note/react/" class="nav-link">react笔记</a></li><li class="dropdown-subitem"><a href="/note/wx/" class="nav-link">微信小程序笔记</a></li><li class="dropdown-subitem"><a href="/note/uniapp/" class="nav-link">uniapp笔记</a></li><li class="dropdown-subitem"><a href="/note/echarts/" class="nav-link">echarts笔记</a></li><li class="dropdown-subitem"><a href="/note/git/" class="nav-link">Git笔记</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="后端" class="dropdown-title"><a href="/back/" class="link-title">后端</a> <span class="title" style="display:none;">后端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/java/" class="nav-link">JAVA</a></li><li class="dropdown-item"><!----> <a href="/note/javaweb/" class="nav-link">JavaWeb</a></li><li class="dropdown-item"><!----> <a href="/note/mysql/" class="nav-link">MySql</a></li><li class="dropdown-item"><!----> <a href="/note/ssm/" class="nav-link">ssm</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法" class="dropdown-title"><a href="/algor/" class="link-title">算法</a> <span class="title" style="display:none;">算法</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/sf/" class="nav-link">算法训练营</a></li><li class="dropdown-item"><!----> <a href="/note/js-sf/" class="nav-link">js数据结构与算法</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="面试" class="dropdown-title"><a href="/mianshi/" class="link-title">面试</a> <span class="title" style="display:none;">面试</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/lqb/" class="nav-link">蓝桥杯备战</a></li><li class="dropdown-item"><!----> <a href="/note/ms/" class="nav-link">前端面试</a></li><li class="dropdown-item"><!----> <a href="/note/hmms/" class="nav-link">黑马面试</a></li><li class="dropdown-item"><!----> <a href="/note/xzms/" class="nav-link">校招零距离面试</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="解决方案" class="dropdown-title"><a href="/resolve/" class="link-title">解决方案</a> <span class="title" style="display:none;">解决方案</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/qd-resolve/" class="nav-link">前端解决方案</a></li><li class="dropdown-item"><!----> <a href="/note/hd-resolve/" class="nav-link">后端解决方案</a></li></ul></div></div><div class="nav-item"><a href="/pages/beb6c0bd8a66cea6/" class="nav-link">收藏</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="索引" class="dropdown-title"><a href="/archives/" class="link-title">索引</a> <span class="title" style="display:none;">索引</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">分类</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">标签</a></li><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">归档</a></li></ul></div></div> <a href="https://github.com/linxin1123/vuepress-blog" target="_blank" rel="noopener noreferrer" class="repo-link">
    GitHub
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar-hover-trigger"></div> <aside class="sidebar" style="display:none;"><div class="blogger"><img src="https://lingxin-tanhua.oss-cn-shanghai.aliyuncs.com/QQ%E6%88%AA%E5%9B%BE20220503092755.png"> <div class="blogger-info"><h3>lingxin</h3> <span>凌歆</span></div></div> <nav class="nav-links"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端" class="dropdown-title"><a href="/web/" class="link-title">前端</a> <span class="title" style="display:none;">前端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>学习笔记</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/note/html/" class="nav-link">HTML笔记</a></li><li class="dropdown-subitem"><a href="/note/js-low/" class="nav-link">JavaScript基础笔记</a></li><li class="dropdown-subitem"><a href="/note/js-high/" class="nav-link">JavaScript高阶笔记</a></li><li class="dropdown-subitem"><a href="/note/js-dom-bom/" class="nav-link">JavaScript DOM和BOM笔记</a></li><li class="dropdown-subitem"><a href="/note/jquery/" class="nav-link">jQuery笔记</a></li><li class="dropdown-subitem"><a href="/note/ajax/" class="nav-link">Ajax笔记</a></li><li class="dropdown-subitem"><a href="/note/nodejs/" class="nav-link">NodeJs笔记</a></li><li class="dropdown-subitem"><a href="/note/reg/" class="nav-link">正则表达式笔记</a></li><li class="dropdown-subitem"><a href="/note/vue/" class="nav-link">Vue笔记</a></li><li class="dropdown-subitem"><a href="/note/react/" class="nav-link">react笔记</a></li><li class="dropdown-subitem"><a href="/note/wx/" class="nav-link">微信小程序笔记</a></li><li class="dropdown-subitem"><a href="/note/uniapp/" class="nav-link">uniapp笔记</a></li><li class="dropdown-subitem"><a href="/note/echarts/" class="nav-link">echarts笔记</a></li><li class="dropdown-subitem"><a href="/note/git/" class="nav-link">Git笔记</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="后端" class="dropdown-title"><a href="/back/" class="link-title">后端</a> <span class="title" style="display:none;">后端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/java/" class="nav-link">JAVA</a></li><li class="dropdown-item"><!----> <a href="/note/javaweb/" class="nav-link">JavaWeb</a></li><li class="dropdown-item"><!----> <a href="/note/mysql/" class="nav-link">MySql</a></li><li class="dropdown-item"><!----> <a href="/note/ssm/" class="nav-link">ssm</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法" class="dropdown-title"><a href="/algor/" class="link-title">算法</a> <span class="title" style="display:none;">算法</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/sf/" class="nav-link">算法训练营</a></li><li class="dropdown-item"><!----> <a href="/note/js-sf/" class="nav-link">js数据结构与算法</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="面试" class="dropdown-title"><a href="/mianshi/" class="link-title">面试</a> <span class="title" style="display:none;">面试</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/lqb/" class="nav-link">蓝桥杯备战</a></li><li class="dropdown-item"><!----> <a href="/note/ms/" class="nav-link">前端面试</a></li><li class="dropdown-item"><!----> <a href="/note/hmms/" class="nav-link">黑马面试</a></li><li class="dropdown-item"><!----> <a href="/note/xzms/" class="nav-link">校招零距离面试</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="解决方案" class="dropdown-title"><a href="/resolve/" class="link-title">解决方案</a> <span class="title" style="display:none;">解决方案</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/qd-resolve/" class="nav-link">前端解决方案</a></li><li class="dropdown-item"><!----> <a href="/note/hd-resolve/" class="nav-link">后端解决方案</a></li></ul></div></div><div class="nav-item"><a href="/pages/beb6c0bd8a66cea6/" class="nav-link">收藏</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="索引" class="dropdown-title"><a href="/archives/" class="link-title">索引</a> <span class="title" style="display:none;">索引</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">分类</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">标签</a></li><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">归档</a></li></ul></div></div> <a href="https://github.com/linxin1123/vuepress-blog" target="_blank" rel="noopener noreferrer" class="repo-link">
    GitHub
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>学习笔记</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>算法训练营</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/pages/8ebdeb/" aria-current="page" class="active sidebar-link">数组-链表-栈-队列-cnblog</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/pages/8585b9/" class="sidebar-link">数组-链表-栈-队列（下）-cnblog</a></li><li><a href="/pages/1848ee/" class="sidebar-link">哈希表-集合-映射-cnblog</a></li><li><a href="/pages/32c8c0/" class="sidebar-link">前缀和-差分-双指针（上）-cnblog</a></li><li><a href="/pages/9b8692/" class="sidebar-link">前缀和-差分-双指针（下）-cnblog</a></li><li><a href="/pages/7f3ede/" class="sidebar-link">算法训练营-排序-cnblog</a></li><li><a href="/pages/cbca68/" class="sidebar-link">二分</a></li><li><a href="/pages/1a456e/" class="sidebar-link">三分-二分答案</a></li><li><a href="/pages/3fd3d8/" class="sidebar-link">树与图-cnblog</a></li><li><a href="/pages/7c3255/" class="sidebar-link">二叉搜索树</a></li><li><a href="/pages/cf81aa/" class="sidebar-link">二叉堆</a></li><li><a href="/pages/1cde21/" class="sidebar-link">递归-分治</a></li><li><a href="/pages/0e21af/" class="sidebar-link">深度-广度搜索-状态空间-cnblog</a></li><li><a href="/pages/6789f3/" class="sidebar-link">动态规划(一)</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>js数据结构与算法</span> <span class="arrow right"></span></p> <!----></section></li></ul> </aside> <div><main class="page"><div class="theme-vdoing-wrapper "><div class="articleInfo-wrap" data-v-06225672><div class="articleInfo" data-v-06225672><ul class="breadcrumbs" data-v-06225672><li data-v-06225672><a href="/" title="首页" class="iconfont icon-home router-link-active" data-v-06225672></a></li> <li data-v-06225672><a href="/algor/#算法" data-v-06225672>算法</a></li><li data-v-06225672><a href="/algor/#算法训练营" data-v-06225672>算法训练营</a></li></ul> <div class="info" data-v-06225672><div title="作者" class="author iconfont icon-touxiang" data-v-06225672><a href="https://github.com/linxin1123" target="_blank" title="作者" class="beLink" data-v-06225672>lingxin</a></div> <div title="创建时间" class="date iconfont icon-riqi" data-v-06225672><a href="javascript:;" data-v-06225672>2023-02-17</a></div> <!----></div></div></div> <!----> <div class="content-wrapper"><div class="right-menu-wrapper"><div class="right-menu-margin"><div class="right-menu-title">目录</div> <div class="right-menu-content"></div></div></div> <h1><img src="">数组-链表-栈-队列-cnblog<!----></h1>  <div class="theme-vdoing-content content__default"><h3 id="变长数组"><a href="#变长数组" class="header-anchor">#</a> 变长数组</h3> <ul><li><p>实现方法（三步）</p></li> <li><p>初始化，分配常数空间</p></li> <li><p>在插入元素的过程中，如果空间不够，新建一个2倍原来空间长度的数组，把原数组的值拷贝到扩容的数组中，释放原数组空间</p></li> <li><p>如果扩容后元素有删除的情况，但总元素个人少于数组长度25，释放一半的空间</p></li> <li><p>时间复杂度分析（==这里n&gt;length才扩容，解释不是非常合理，理解就行==）</p> <ul><li>例如n=5</li></ul> <table><thead><tr><th>数组</th> <th>插入</th> <th>拷贝</th></tr></thead> <tbody><tr><td>[null]</td> <td>0</td> <td>0</td></tr> <tr><td>[1]</td> <td>1</td> <td>0</td></tr> <tr><td>[1,2]</td> <td>2</td> <td>1(次数) 1（元素个数）</td></tr> <tr><td>[1,2,3,null]</td> <td>3</td> <td>1(次数)  2 （元素个数）</td></tr> <tr><td>[1,2,3,4]</td> <td>4</td> <td>0 0</td></tr> <tr><td>[1,2,3,4,5,null,null,null]</td> <td>5</td> <td>1(次数)   4 (元素个数)</td></tr></tbody></table> <ul><li>分析
<ul><li>长度为2是，拷贝1次，转移1个元素</li> <li>长度为3时，拷贝1次，转移2个元素</li> <li>长度为5时，拷贝1次，转移4个元素</li></ul></li> <li>1+3+5 =n+n/2+n/4 即差不多（因为空数组没有另外计算了）</li></ul></li> <li><p>对于其他的n ，n+n/2+n/4+.... &lt;=2n</p></li> <li><p>一次扩容到下一次释放的最小的删除次数（一次删一个）0.5n（==这里使用n=4时进行扩容==）</p> <ul><li>例如上题的n=4</li> <li>n=4时扩容了一次，2n=8</li> <li>还需要删除2，4-2=2（25%,即0.5n）</li></ul></li></ul> <h4 id="注意点"><a href="#注意点" class="header-anchor">#</a> 注意点</h4> <ul><li>可以是n=5是进行扩容</li> <li>也可以是n=4（到达数组长度就进行扩容），这样上述的解释更合理</li> <li>取决于你如何设计，但复杂度分析还是大差不差的</li></ul> <h3 id="leetcode"><a href="#leetcode" class="header-anchor">#</a> LeetCode</h3> <h4 id="_88-合并两个有序数组"><a href="#_88-合并两个有序数组" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/merge-sorted-array/" target="_blank" rel="noopener noreferrer">88. 合并两个有序数组<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给你两个按 <strong>非递减顺序</strong> 排列的整数数组 <code>nums1</code> 和 <code>nums2</code>，另有两个整数 <code>m</code> 和 <code>n</code> ，分别表示 <code>nums1</code> 和 <code>nums2</code> 中的元素数目。</p> <p>请你 <strong>合并</strong> <code>nums2</code> 到 <code>nums1</code> 中，使合并后的数组同样按 <strong>非递减顺序</strong> 排列。</p> <p>**注意：**最终，合并后数组不应由函数返回，而是存储在数组 <code>nums1</code> 中。为了应对这种情况，<code>nums1</code> 的初始长度为 <code>m + n</code>，其中前 <code>m</code> 个元素表示应合并的元素，后 <code>n</code> 个元素为 <code>0</code> ，应忽略。<code>nums2</code> 的长度为 <code>n</code> 。</p> <p><strong>示例 1：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><p><strong>示例 3：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>nums1.length == m + n</code></li> <li><code>nums2.length == n</code></li> <li><code>0 &lt;= m, n &lt;= 200</code></li> <li><code>1 &lt;= m + n &lt;= 200</code></li> <li><code>-109 &lt;= nums1[i], nums2[j] &lt;= 109</code></li></ul> <p>**进阶：**你可以设计实现一个时间复杂度为 <code>O(m + n)</code> 的算法解决此问题吗？</p> <h5 id="朴素算法"><a href="#朴素算法" class="header-anchor">#</a> 朴素算法</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">merge</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">nums1<span class="token punctuation">,</span> m<span class="token punctuation">,</span> nums2<span class="token punctuation">,</span> n</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 合并两个有序数组</span>
    <span class="token comment">// 升序排列</span>

    <span class="token comment">// 1.朴素算法 </span>
    <span class="token comment">// 定义一个m+n长度的数组，存放排序好的</span>

    <span class="token comment">// 定义三个指针，分别是nums1移动下标，nums2的移动下标</span>

    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    <span class="token keyword">let</span> p1<span class="token operator">=</span><span class="token number">0</span>
    <span class="token keyword">let</span> p2<span class="token operator">=</span><span class="token number">0</span>
    <span class="token comment">// let p3=0</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>p1<span class="token operator">&lt;</span>m<span class="token operator">&amp;&amp;</span>p2<span class="token operator">&lt;</span>n<span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>nums1<span class="token punctuation">[</span>p1<span class="token punctuation">]</span><span class="token operator">&gt;</span>nums2<span class="token punctuation">[</span>p2<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>nums2<span class="token punctuation">[</span>p2<span class="token punctuation">]</span><span class="token punctuation">)</span>
            <span class="token comment">// console.log(nums2[p2])</span>
            p2<span class="token operator">++</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span> <span class="token punctuation">{</span>
            res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>nums1<span class="token punctuation">[</span>p1<span class="token punctuation">]</span><span class="token punctuation">)</span>
            <span class="token comment">// console.log(nums1[p1])</span>
            p1<span class="token operator">++</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>p1<span class="token operator">&lt;</span>m<span class="token punctuation">)</span><span class="token punctuation">{</span>
        res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>nums1<span class="token punctuation">[</span>p1<span class="token punctuation">]</span><span class="token punctuation">)</span>
        <span class="token comment">// console.log(nums1[p1])</span>
        p1<span class="token operator">++</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">while</span><span class="token punctuation">(</span>p2<span class="token operator">&lt;</span>n<span class="token punctuation">)</span><span class="token punctuation">{</span>
        res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>nums2<span class="token punctuation">[</span>p2<span class="token punctuation">]</span><span class="token punctuation">)</span>
        <span class="token comment">// console.log(nums2[p2])</span>
        p2<span class="token operator">++</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// console.log(res)</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> k<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>k<span class="token operator">&lt;</span>m<span class="token operator">+</span>n<span class="token punctuation">;</span>k<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        nums1<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">=</span>res<span class="token punctuation">[</span>k<span class="token punctuation">]</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// return res</span>
    

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br></div></div><ul><li>时间复杂度：O(m+n)  准确 2*（m+n）</li> <li>空间复杂度：O(m+n)</li></ul> <h5 id="优化版本"><a href="#优化版本" class="header-anchor">#</a> 优化版本</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">merge</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">nums1<span class="token punctuation">,</span> m<span class="token punctuation">,</span> nums2<span class="token punctuation">,</span> n</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 合并两个有序数组</span>
    <span class="token comment">// 升序排列</span>

    
    <span class="token comment">// 2. 优化版本</span>

    <span class="token comment">// 从nums1的最后下标开始，选取大的放入</span>

    <span class="token comment">// 定义两个指针，分别指向 nums1，nums2的最后一个元素</span>

    <span class="token keyword">let</span> i<span class="token operator">=</span>m<span class="token operator">-</span><span class="token number">1</span>
    <span class="token keyword">let</span> j<span class="token operator">=</span>n<span class="token operator">-</span><span class="token number">1</span>
    <span class="token keyword">let</span> k<span class="token operator">=</span>m<span class="token operator">+</span>n<span class="token operator">-</span><span class="token number">1</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token punctuation">;</span>k<span class="token operator">&gt;=</span><span class="token number">0</span><span class="token punctuation">;</span>k<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token comment">// 出口，如果i或者j小于0</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">&lt;</span><span class="token number">0</span><span class="token operator">||</span>j<span class="token operator">&lt;</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>nums1<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">&gt;</span>nums2<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            nums1<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">=</span>nums1<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            i<span class="token operator">--</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span>
            nums1<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">=</span>nums2<span class="token punctuation">[</span>j<span class="token punctuation">]</span>
            j<span class="token operator">--</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// i最大的全部被挑选了</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>j<span class="token operator">&gt;=</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        nums1<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>nums2<span class="token punctuation">[</span>j<span class="token punctuation">]</span>
        j<span class="token operator">--</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// j最大的全部被挑选了</span>
    <span class="token comment">// while(i&gt;=0){</span>
    <span class="token comment">//     // 什么都不用做，因为i对于数组有序</span>
    <span class="token comment">// }</span>

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br></div></div><ul><li>时间复杂度O(m+n)  准确m+n</li> <li>空间复杂度O(1)</li></ul> <h5 id="堆排版本-更适用于有n个有序数组的合并"><a href="#堆排版本-更适用于有n个有序数组的合并" class="header-anchor">#</a> 堆排版本(更适用于有n个有序数组的合并)</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 使用最大堆
<span class="token number">2</span>. 先把每个数组头<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>入堆
<span class="token number">3</span>. 开始最小的出堆，同时把其后面一个元素入堆<span class="token punctuation">[</span><span class="token number">0</span>+1<span class="token punctuation">(</span>可变<span class="token punctuation">)</span><span class="token punctuation">]</span>
<span class="token number">4</span>. 直到堆为空
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><ul><li>需要维护一个指针数组，每个数组的后继元素</li> <li>以本题为例
<ul><li>时间复杂度mlog(2)+m+nlog(2)+n ,2O(m+n)</li> <li>空间复杂度 2(数组个数)</li></ul></li></ul> <h4 id="_26-删除有序数组中的重复项-模板题"><a href="#_26-删除有序数组中的重复项-模板题" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/remove-duplicates-from-sorted-array/" target="_blank" rel="noopener noreferrer">26. 删除有序数组中的重复项（模板题）<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给你一个 <strong>升序排列</strong> 的数组 <code>nums</code> ，请你**<a href="http://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95" target="_blank" rel="noopener noreferrer"> 原地<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>** 删除重复出现的元素，使每个元素 <strong>只出现一次</strong> ，返回删除后数组的新长度。元素的 <strong>相对顺序</strong> 应该保持 <strong>一致</strong> 。</p> <p>由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 <code>k</code> 个元素，那么 <code>nums</code> 的前 <code>k</code> 个元素应该保存最终结果。</p> <p>将最终结果插入 <code>nums</code> 的前 <code>k</code> 个位置后返回 <code>k</code> 。</p> <p>不要使用额外的空间，你必须在 <strong><a href="https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95" target="_blank" rel="noopener noreferrer">原地 <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>修改输入数组</strong> 并在使用 O(1) 额外空间的条件下完成。</p> <p><strong>判题标准:</strong></p> <p>系统会用下面的代码来测试你的题解:</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i &lt; k; i++) {
    assert nums[i] == expectedNums[i];
}
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br></div></div><p>如果所有断言都通过，那么您的题解将被 <strong>通过</strong>。</p> <p><strong>示例 1：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>1 &lt;= nums.length &lt;= 3 * 104</code></li> <li><code>-104 &lt;= nums[i] &lt;= 104</code></li> <li><code>nums</code> 已按 <strong>升序</strong> 排列</li></ul> <h5 id="解题思路"><a href="#解题思路" class="header-anchor">#</a> 解题思路</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token number">1.</span>数组升序<span class="token punctuation">,</span>原地去重
<span class="token number">2.</span>找出数组中所有不同的元素
<span class="token number">3.</span>遍历数组，判断数组元素不相同
<span class="token number">4.</span>数组元素不相同（因为数组有序，则分界点<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token punctuation">[</span>i<span class="token punctuation">]</span> 不同）

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><ul><li>==5.思想：==
==不同则选取==</li></ul> <h5 id="完整代码"><a href="#完整代码" class="header-anchor">#</a> 完整代码</h5> <div class="language-java line-numbers-mode"><pre class="language-java"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">removeDuplicates</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 思路，遍历数组，判断是否需要保留该数</span>
        <span class="token keyword">int</span> cnt<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>nums<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                cnt<span class="token operator">++</span><span class="token punctuation">;</span>
                <span class="token keyword">continue</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span> 
            <span class="token keyword">if</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">!=</span>nums<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                nums<span class="token punctuation">[</span>cnt<span class="token punctuation">]</span><span class="token operator">=</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
                cnt<span class="token operator">++</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> cnt<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br></div></div><h4 id="_283-移动零-模板题"><a href="#_283-移动零-模板题" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/move-zeroes/" target="_blank" rel="noopener noreferrer">283. 移动零(模板题)<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <ul><li>==该题与上题26-删除有序数组的重复思想相同（满足条件则选取）==</li></ul> <p>给定一个数组 <code>nums</code>，编写一个函数将所有 <code>0</code> 移动到数组的末尾，同时保持非零元素的相对顺序。</p> <p><strong>请注意</strong> ，必须在不复制数组的情况下原地对数组进行操作。</p> <p><strong>示例 1:</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 2:</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入: nums = [0]
输出: [0]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示</strong>:</p> <ul><li><code>1 &lt;= nums.length &lt;= 104</code></li> <li><code>-231 &lt;= nums[i] &lt;= 231 - 1</code></li></ul> <p>**进阶：**你能尽量减少完成的操作次数吗？</p> <h5 id="完整代码-2"><a href="#完整代码-2" class="header-anchor">#</a> 完整代码</h5> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token keyword">void</span> <span class="token function">moveZeroes</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>

        <span class="token comment">// 解题思路</span>
        <span class="token comment">// 满足条件的放前面</span>
        <span class="token keyword">int</span> n<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">!=</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                nums<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token operator">=</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
                n<span class="token operator">++</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token punctuation">;</span>n<span class="token operator">&lt;</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>n<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            nums<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br></div></div><h4 id="_206-反转链表"><a href="#_206-反转链表" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/reverse-linked-list/" target="_blank" rel="noopener noreferrer">206. 反转链表<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给你单链表的头节点 <code>head</code> ，请你反转链表，并返回反转后的链表。</p> <p><strong>示例 1：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 2：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：head = [1,2]
输出：[2,1]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 3：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：head = []
输出：[]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li>链表中节点的数目范围是 <code>[0, 5000]</code></li> <li><code>-5000 &lt;= Node.val &lt;= 5000</code></li></ul> <p>**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？</p> <h5 id="解题思路-2"><a href="#解题思路-2" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 反转链表，即每个节点指向需要发生改变
<span class="token number">2</span>. 需要改n次
<span class="token number">3</span>. 遍历该链表
<span class="token number">4</span>. 每到达一个节点，改变指向为前一个节点，（同时把该节点存储为前一个节点）（方便后面元素使用）
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br></div></div><h5 id="完整代码-3"><a href="#完整代码-3" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */</span>
<span class="token comment">/**
 * @param {ListNode} head
 * @return {ListNode}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">reverseList</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 更换链条的顺序，更换n次</span>

    <span class="token keyword">let</span> pre<span class="token operator">=</span><span class="token keyword">null</span><span class="token punctuation">;</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> p<span class="token operator">=</span>head<span class="token punctuation">;</span>p<span class="token operator">!=</span><span class="token keyword">null</span><span class="token punctuation">;</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">let</span> nextNode<span class="token operator">=</span>p<span class="token punctuation">.</span>next

        p<span class="token punctuation">.</span>next<span class="token operator">=</span>pre

        pre<span class="token operator">=</span>p

        
        p<span class="token operator">=</span>nextNode
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> pre<span class="token punctuation">;</span>

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br></div></div><h4 id="_136-邻值查找-可选"><a href="#_136-邻值查找-可选" class="header-anchor">#</a> 136. 邻值查找（可选）</h4> <p>给定一个长度为 nn 的序列 AA，AA 中的数各不相同。</p> <p>对于 AA 中的每一个数 AiAi，求：</p> <p>min1≤j&lt;i|Ai−Aj|min1≤j&lt;i|Ai−Aj|</p> <p>以及令上式取到最小值的 jj（记为 PiPi）。若最小值点不唯一，则选择使 AjAj 较小的那个。</p> <h5 id="输入格式"><a href="#输入格式" class="header-anchor">#</a> 输入格式</h5> <p>第一行输入整数 nn，代表序列长度。</p> <p>第二行输入 nn 个整数A1…AnA1…An,代表序列的具体数值，数值之间用空格隔开。</p> <h5 id="输出格式"><a href="#输出格式" class="header-anchor">#</a> 输出格式</h5> <p>输出共 n−1n−1 行，每行输出两个整数，数值之间用空格隔开。</p> <p>分别表示当 ii 取 2∼n2∼n 时，对应的 min1≤j&lt;i|Ai−Aj|min1≤j&lt;i|Ai−Aj| 和 PiPi 的值。</p> <h5 id="数据范围"><a href="#数据范围" class="header-anchor">#</a> 数据范围</h5> <p>n≤105n≤105,|Ai|≤109|Ai|≤109</p> <h5 id="输入样例"><a href="#输入样例" class="header-anchor">#</a> 输入样例：</h5> <div class="language- line-numbers-mode"><pre class="language-text"><code>3
1 5 3
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><h5 id="输出样例"><a href="#输出样例" class="header-anchor">#</a> 输出样例：</h5> <div class="language- line-numbers-mode"><pre class="language-text"><code>4 1
2 1
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><h5 id="解题思路-3"><a href="#解题思路-3" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 从下标2开始，找在它前面的元素（元素的值-当前值最小），输出差值和找到元素的下标
<span class="token number">2</span>. 如果使用朴素算法 <span class="token number">1</span>*2*3*。。。*n n<span class="token operator">!</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><div class="language-shell line-numbers-mode"><pre class="language-shell"><code>正确解法
<span class="token number">1</span>. 为每个元素先创建节点（val和下标）n
<span class="token number">2</span>. 对节点进行排序 nlog<span class="token punctuation">(</span>n<span class="token punctuation">)</span>
<span class="token number">3</span>. 把排序后的节点连接起来（双向链表）n
<span class="token number">4</span>. 定义一个数组，存储没有排序的节点
<span class="token number">5</span>. 从5数组的最后一个下标（一个节点-<span class="token operator">&gt;</span>对应排序后双向链表中的一个节	点）开始，比较它的前驱和后继与该节点值的差值 n
	看那个小，输出该查找和较小的下标
<span class="token number">6</span>. 删除双向链表中数组5最后一个节点 <span class="token number">1</span>*n
<span class="token number">7</span>. <span class="token number">5</span>的下标左移，重新循环5,6,7，直到下标<span class="token operator">=</span><span class="token number">1</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br></div></div><ul><li><p>注意点</p> <ul><li>==从5数组的最后一个下标开始==，因为可以保证==它的前驱和后继的下标都在它前面==</li> <li>删除5数组在双向链表中的对应节点（==可以保证其他的元素节点的前驱和后继都是在本身下标的前面）==</li> <li>比较它的前驱和后继与该节点值的差值 （==因为排序后，节点附近的差值一定是最小的）==</li></ul></li> <li><p>时间复杂度</p> <ul><li>n+nlogn+n+n+n ==&gt;O(n+nlog(n))</li></ul></li> <li><p>空间复杂度</p> <ul><li>n+n==&gt;O(n)</li></ul></li></ul> <h5 id="完整代码-4"><a href="#完整代码-4" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token keyword">let</span> arr <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">]</span>

<span class="token comment">// 存储节点，用于构建双向链表</span>
<span class="token keyword">function</span> <span class="token function">Node</span><span class="token punctuation">(</span><span class="token parameter">val<span class="token punctuation">,</span> index<span class="token punctuation">,</span> pre<span class="token punctuation">,</span> next</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>val <span class="token operator">=</span> val <span class="token operator">===</span> <span class="token keyword">undefined</span> <span class="token operator">?</span> <span class="token operator">-</span><span class="token number">1</span> <span class="token operator">:</span> val
  <span class="token keyword">this</span><span class="token punctuation">.</span>index <span class="token operator">=</span> index <span class="token operator">===</span> <span class="token keyword">undefined</span> <span class="token operator">?</span> <span class="token operator">-</span><span class="token number">2</span> <span class="token operator">:</span> index
  <span class="token keyword">this</span><span class="token punctuation">.</span>pre <span class="token operator">=</span> pre <span class="token operator">===</span> <span class="token keyword">undefined</span> <span class="token operator">?</span> <span class="token keyword">null</span> <span class="token operator">:</span> pre
  <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> next <span class="token operator">===</span> <span class="token keyword">undefined</span> <span class="token operator">?</span> <span class="token keyword">null</span> <span class="token operator">:</span> next
<span class="token punctuation">}</span>

<span class="token comment">// 创建保护节点</span>
<span class="token keyword">let</span> head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
<span class="token keyword">let</span> tail <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span>

head<span class="token punctuation">.</span>next <span class="token operator">=</span> tail
tail<span class="token punctuation">.</span>pre <span class="token operator">=</span> head
<span class="token comment">// 创建保护节点</span>

<span class="token comment">// 创建元素节点</span>
<span class="token keyword">let</span> nodeList <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
<span class="token keyword">let</span> nodeList2 <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
arr<span class="token punctuation">.</span><span class="token function">forEach</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token parameter">item<span class="token punctuation">,</span> index</span><span class="token punctuation">)</span> <span class="token operator">=&gt;</span> <span class="token punctuation">{</span>
  <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>item<span class="token punctuation">,</span> index<span class="token punctuation">)</span>
  nodeList<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span>
  nodeList2<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span>
<span class="token punctuation">}</span><span class="token punctuation">)</span>

<span class="token comment">// 节点排序</span>
nodeList<span class="token punctuation">.</span><span class="token function">sort</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token parameter">a<span class="token punctuation">,</span> b</span><span class="token punctuation">)</span> <span class="token operator">=&gt;</span> <span class="token punctuation">{</span>
  <span class="token keyword">return</span> a<span class="token punctuation">.</span>val <span class="token operator">-</span> b<span class="token punctuation">.</span>val
<span class="token punctuation">}</span><span class="token punctuation">)</span>

<span class="token comment">// 创建双向链表（排序后的）</span>
<span class="token keyword">let</span> pTail <span class="token operator">=</span> head
nodeList<span class="token punctuation">.</span><span class="token function">forEach</span><span class="token punctuation">(</span><span class="token parameter">item</span> <span class="token operator">=&gt;</span> <span class="token punctuation">{</span>
  pTail<span class="token punctuation">.</span>next <span class="token operator">=</span> item
  item<span class="token punctuation">.</span>pre <span class="token operator">=</span> pTail
  pTail <span class="token operator">=</span> pTail<span class="token punctuation">.</span>next
<span class="token punctuation">}</span><span class="token punctuation">)</span>

nodeList<span class="token punctuation">[</span>nodeList<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>next <span class="token operator">=</span> tail
tail<span class="token punctuation">.</span>pre <span class="token operator">=</span> nodeList<span class="token punctuation">[</span>nodeList<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span>


<span class="token comment">// nodeList2 从最后一个元素开始</span>
<span class="token comment">// 比较前驱和后继</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> nodeList2<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&gt;=</span> <span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">let</span> a <span class="token operator">=</span> <span class="token number">0</span> <span class="token comment">// 前驱差值绝对值</span>
  <span class="token keyword">let</span> b <span class="token operator">=</span> <span class="token number">0</span> <span class="token comment">// 后继差值绝对值</span>
  <span class="token keyword">let</span> res <span class="token operator">=</span> <span class="token number">0</span> <span class="token comment">// 差值绝对值最小值</span>
  <span class="token keyword">let</span> index <span class="token operator">=</span> <span class="token number">0</span> <span class="token comment">// 找到的下标</span>
  
  <span class="token keyword">if</span> <span class="token punctuation">(</span>nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>pre<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    a <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">abs</span><span class="token punctuation">(</span>nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>val <span class="token operator">-</span> nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>pre<span class="token punctuation">.</span>val<span class="token punctuation">)</span>
  <span class="token punctuation">}</span>

  <span class="token keyword">if</span> <span class="token punctuation">(</span>nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>next<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    b <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">abs</span><span class="token punctuation">(</span>nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>val <span class="token operator">-</span> nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>next<span class="token punctuation">.</span>val<span class="token punctuation">)</span>
  <span class="token punctuation">}</span>

  <span class="token keyword">if</span> <span class="token punctuation">(</span>a <span class="token operator">&gt;</span> b<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    res <span class="token operator">=</span> b
    index <span class="token operator">=</span> nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>next<span class="token punctuation">.</span>index
  <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>a <span class="token operator">&lt;</span> b<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    res <span class="token operator">=</span> a
    index <span class="token operator">=</span> nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>pre<span class="token punctuation">.</span>index
  <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
    res <span class="token operator">=</span> a
    index <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">min</span><span class="token punctuation">(</span>nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>pre<span class="token punctuation">.</span>index<span class="token punctuation">,</span> nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>next<span class="token punctuation">.</span>index<span class="token punctuation">)</span>
  <span class="token punctuation">}</span>

  console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>res<span class="token punctuation">,</span> index <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> i<span class="token punctuation">)</span>

  <span class="token comment">// 把当前节点删除</span>
  <span class="token keyword">let</span> pre1 <span class="token operator">=</span> nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>pre
  nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>pre<span class="token punctuation">.</span>next <span class="token operator">=</span> nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>next
  nodeList2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>next<span class="token punctuation">.</span>pre <span class="token operator">=</span> pre1
<span class="token punctuation">}</span>

console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>nodeList<span class="token punctuation">)</span>

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br></div></div><h4 id="_142-环形链表-ii-可选"><a href="#_142-环形链表-ii-可选" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/linked-list-cycle-ii/" target="_blank" rel="noopener noreferrer">142. 环形链表 II(可选)<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给定一个链表的头节点  <code>head</code> ，返回链表开始入环的第一个节点。 <em>如果链表无环，则返回 <code>null</code>。</em></p> <p>如果链表中有某个节点，可以通过连续跟踪 <code>next</code> 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 <code>pos</code> 来表示链表尾连接到链表中的位置（<strong>索引从 0 开始</strong>）。如果 <code>pos</code> 是 <code>-1</code>，则在该链表中没有环。<strong>注意：<code>pos</code> 不作为参数进行传递</strong>，仅仅是为了标识链表的实际情况。</p> <p><strong>不允许修改</strong> 链表。</p> <p><strong>示例 1：</strong></p> <p><img src="https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 2：</strong></p> <p><img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test2.png" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 3：</strong></p> <p><img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test3.png" alt="img"></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>提示：</strong></p> <ul><li>链表中节点的数目范围在范围 <code>[0, 104]</code> 内</li> <li><code>-105 &lt;= Node.val &lt;= 105</code></li> <li><code>pos</code> 的值为 <code>-1</code> 或者链表中的一个有效索引</li></ul> <p>**进阶：**你是否可以使用 <code>O(1)</code> 空间解决此题？</p> <h5 id="解题思路-4"><a href="#解题思路-4" class="header-anchor">#</a> 解题思路</h5> <ul><li>快慢指针
<ul><li>快的一次走两步</li> <li>慢的一次走一步</li> <li>如果存在环，必定相遇</li></ul></li></ul> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 判断是否存在环，不存在，直接返回
<span class="token number">2</span>. 存在，在相遇点，假设快指针走了l+p+kr<span class="token punctuation">(</span>r为环的长度<span class="token punctuation">)</span>，慢指针走了
l+p
<span class="token number">3</span>. 则2<span class="token punctuation">(</span>l+p<span class="token punctuation">)</span><span class="token operator">=</span>l+p+kr<span class="token operator">==</span>》l<span class="token operator">=</span><span class="token punctuation">(</span>k-1<span class="token punctuation">)</span>*r+<span class="token punctuation">(</span>r-p<span class="token punctuation">)</span>

<span class="token number">4</span>. 即l<span class="token operator">=</span>r-p+k倍环的长度

<span class="token number">5</span>.则head一次走一步，慢指针重相遇点一次走一步，必定在起点相遇
	
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br></div></div><ul><li><img src="https://img2023.cnblogs.com/blog/3089561/202302/3089561-20230203130716604-1080168296.png" alt=""></li></ul> <h5 id="完整代码-5"><a href="#完整代码-5" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */</span>

<span class="token comment">/**
 * @param {ListNode} head
 * @return {ListNode}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">detectCycle</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">head</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 定义一个是否有环的判断函数</span>

    <span class="token keyword">const</span> <span class="token function-variable function">hasCircle</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">head</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>

        <span class="token keyword">let</span> fast<span class="token operator">=</span>head<span class="token punctuation">;</span>
        <span class="token keyword">let</span> slow<span class="token operator">=</span>head<span class="token punctuation">;</span>

        <span class="token keyword">while</span><span class="token punctuation">(</span>fast<span class="token operator">!=</span><span class="token keyword">null</span><span class="token operator">&amp;&amp;</span>slow<span class="token operator">!=</span><span class="token keyword">null</span><span class="token operator">&amp;&amp;</span>fast<span class="token punctuation">.</span>next<span class="token operator">!=</span><span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            fast<span class="token operator">=</span>fast<span class="token punctuation">.</span>next<span class="token punctuation">.</span>next
            slow<span class="token operator">=</span>slow<span class="token punctuation">.</span>next

            <span class="token keyword">if</span><span class="token punctuation">(</span>fast<span class="token operator">===</span>slow<span class="token punctuation">)</span><span class="token punctuation">{</span>
                <span class="token keyword">return</span> slow
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> <span class="token keyword">null</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">let</span> slow<span class="token operator">=</span><span class="token function">hasCircle</span><span class="token punctuation">(</span>head<span class="token punctuation">)</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>slow<span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">null</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 有环，返回起点的下标</span>

    <span class="token comment">// head 和slow相遇点同时开始走，再次相遇就是start</span>

    <span class="token keyword">let</span> p<span class="token operator">=</span>head
    <span class="token keyword">while</span><span class="token punctuation">(</span>p<span class="token operator">!==</span>slow<span class="token punctuation">)</span><span class="token punctuation">{</span>
        p<span class="token operator">=</span>p<span class="token punctuation">.</span>next
        slow<span class="token operator">=</span>slow<span class="token punctuation">.</span>next
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> p
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br></div></div><h4 id="_155-最小栈"><a href="#_155-最小栈" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/min-stack/" target="_blank" rel="noopener noreferrer">155. 最小栈<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>设计一个支持 <code>push</code> ，<code>pop</code> ，<code>top</code> 操作，并能在常数时间内检索到最小元素的栈。</p> <p>实现 <code>MinStack</code> 类:</p> <ul><li><code>MinStack()</code> 初始化堆栈对象。</li> <li><code>void push(int val)</code> 将元素val推入堆栈。</li> <li><code>void pop()</code> 删除堆栈顶部的元素。</li> <li><code>int top()</code> 获取堆栈顶部的元素。</li> <li><code>int getMin()</code> 获取堆栈中的最小元素。</li></ul> <p><strong>示例 1:</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：
[&quot;MinStack&quot;,&quot;push&quot;,&quot;push&quot;,&quot;push&quot;,&quot;getMin&quot;,&quot;pop&quot;,&quot;top&quot;,&quot;getMin&quot;]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --&gt; 返回 -3.
minStack.pop();
minStack.top();      --&gt; 返回 0.
minStack.getMin();   --&gt; 返回 -2.
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>-231 &lt;= val &lt;= 231 - 1</code></li> <li><code>pop</code>、<code>top</code> 和 <code>getMin</code> 操作总是在 <strong>非空栈</strong> 上调用</li> <li><code>push</code>, <code>pop</code>, <code>top</code>, and <code>getMin</code>最多被调用 <code>3 * 104</code> 次</li></ul> <h5 id="解题思路-5"><a href="#解题思路-5" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code>获取栈的最小值
<span class="token number">1</span>. 在每个元素入栈时比较，当前元素和栈顶元素的大小，把较小值存储起来
<span class="token number">2</span>. 弹栈时，栈顶元素出去，存储的较小值也出去
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><h5 id="完整代码-6"><a href="#完整代码-6" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code>
<span class="token comment">// 解题思路</span>

<span class="token comment">// 定义一个辅助栈</span>

<span class="token comment">// 每次进来时，辅助站只存储栈的最小值</span>

<span class="token comment">// 当获取栈的最小值时，最小值就在辅助栈栈顶</span>

<span class="token keyword">var</span> <span class="token function-variable function">MinStack</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>stack<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>minStack<span class="token operator">=</span><span class="token punctuation">[</span><span class="token number">Infinity</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">/** 
 * @param {number} val
 * @return {void}
 */</span>
<span class="token class-name">MinStack</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">push</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">val</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>val<span class="token punctuation">)</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>minStack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>Math<span class="token punctuation">.</span><span class="token function">min</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>minStack<span class="token punctuation">[</span><span class="token keyword">this</span><span class="token punctuation">.</span>minStack<span class="token punctuation">.</span>length<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span>val<span class="token punctuation">)</span><span class="token punctuation">)</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">/**
 * @return {void}
 */</span>
<span class="token class-name">MinStack</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">pop</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>stack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span>minStack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">/**
 * @return {number}
 */</span>
<span class="token class-name">MinStack</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">top</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>stack<span class="token punctuation">.</span>length<span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>stack<span class="token punctuation">[</span><span class="token keyword">this</span><span class="token punctuation">.</span>stack<span class="token punctuation">.</span>length<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> <span class="token keyword">undefined</span>   
<span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">/**
 * @return {number}
 */</span>
<span class="token class-name">MinStack</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">getMin</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>minStack<span class="token punctuation">[</span><span class="token keyword">this</span><span class="token punctuation">.</span>minStack<span class="token punctuation">.</span>length<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>

<span class="token comment">/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br></div></div><h4 id="_150-逆波兰表达式求值"><a href="#_150-逆波兰表达式求值" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/evaluate-reverse-polish-notation/" target="_blank" rel="noopener noreferrer">150. 逆波兰表达式求值<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>根据<a href="https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437" target="_blank" rel="noopener noreferrer"> 逆波兰表示法<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>，求表达式的值。</p> <p>有效的算符包括 <code>+</code>、<code>-</code>、<code>*</code>、<code>/</code> 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。</p> <p><strong>注意</strong> 两个整数之间的除法只保留整数部分。</p> <p>可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。</p> <p><strong>示例 1：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：tokens = [&quot;2&quot;,&quot;1&quot;,&quot;+&quot;,&quot;3&quot;,&quot;*&quot;]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：tokens = [&quot;4&quot;,&quot;13&quot;,&quot;5&quot;,&quot;/&quot;,&quot;+&quot;]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><p><strong>示例 3：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：tokens = [&quot;10&quot;,&quot;6&quot;,&quot;9&quot;,&quot;3&quot;,&quot;+&quot;,&quot;-11&quot;,&quot;*&quot;,&quot;/&quot;,&quot;*&quot;,&quot;17&quot;,&quot;+&quot;,&quot;5&quot;,&quot;+&quot;]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>1 &lt;= tokens.length &lt;= 104</code></li> <li><code>tokens[i]</code> 是一个算符（<code>&quot;+&quot;</code>、<code>&quot;-&quot;</code>、<code>&quot;*&quot;</code> 或 <code>&quot;/&quot;</code>），或是在范围 <code>[-200, 200]</code> 内的一个整数</li></ul> <p><strong>逆波兰表达式：</strong></p> <p>逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。</p> <ul><li>平常使用的算式则是一种中缀表达式，如 <code>( 1 + 2 ) * ( 3 + 4 )</code> 。</li> <li>该算式的逆波兰表达式写法为 <code>( ( 1 2 + ) ( 3 4 + ) * )</code> 。</li></ul> <p>逆波兰表达式主要有以下两个优点：</p> <ul><li>去掉括号后表达式无歧义，上式即便写成 <code>1 2 + 3 4 + *</code>也可以依据次序计算出正确结果。</li> <li>适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中</li></ul> <h5 id="完整代码-7"><a href="#完整代码-7" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {string[]} tokens
 * @return {number}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">evalRPN</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">tokens</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 后缀表达式求值</span>

    <span class="token comment">// 存在最近相关性，一般用栈解决</span>

    <span class="token comment">// 遇到数字，入栈</span>

    <span class="token comment">// 遇到运算符，出栈两个运算数，结果压入栈中</span>

    <span class="token keyword">let</span> stack<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    <span class="token keyword">const</span> <span class="token function-variable function">compute</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">ch</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
        <span class="token keyword">let</span> a<span class="token operator">=</span>stack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token keyword">let</span> b<span class="token operator">=</span>stack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token keyword">switch</span><span class="token punctuation">(</span>ch<span class="token punctuation">)</span><span class="token punctuation">{</span>

            <span class="token keyword">case</span> <span class="token string">&quot;+&quot;</span><span class="token operator">:</span>
                <span class="token keyword">return</span> a<span class="token operator">+</span>b
            <span class="token keyword">break</span>
            <span class="token keyword">case</span> <span class="token string">&quot;-&quot;</span><span class="token operator">:</span>
                <span class="token keyword">return</span> b<span class="token operator">-</span>a
            <span class="token keyword">break</span>
            <span class="token keyword">case</span> <span class="token string">&quot;*&quot;</span><span class="token operator">:</span>
                <span class="token keyword">return</span> b<span class="token operator">*</span>a
            <span class="token keyword">break</span>
            <span class="token keyword">case</span> <span class="token string">&quot;/&quot;</span><span class="token operator">:</span>
                <span class="token keyword">return</span> Number<span class="token punctuation">.</span><span class="token function">parseInt</span><span class="token punctuation">(</span>b<span class="token operator">/</span>a<span class="token punctuation">)</span> 
            <span class="token keyword">break</span>  
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">let</span> chArr<span class="token operator">=</span><span class="token punctuation">[</span><span class="token string">&quot;+&quot;</span><span class="token punctuation">,</span><span class="token string">&quot;-&quot;</span><span class="token punctuation">,</span><span class="token string">&quot;*&quot;</span><span class="token punctuation">,</span><span class="token string">&quot;/&quot;</span><span class="token punctuation">]</span>

    tokens<span class="token punctuation">.</span><span class="token function">forEach</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token parameter">item</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>chArr<span class="token punctuation">.</span><span class="token function">some</span><span class="token punctuation">(</span><span class="token parameter">item1</span><span class="token operator">=&gt;</span>item1<span class="token operator">===</span>item<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token function">compute</span><span class="token punctuation">(</span>item<span class="token punctuation">)</span>
            stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>res<span class="token punctuation">)</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span>
            <span class="token comment">// 转换成数字</span>
            <span class="token keyword">let</span> num<span class="token operator">=</span>Number<span class="token punctuation">.</span><span class="token function">parseInt</span><span class="token punctuation">(</span>item<span class="token punctuation">)</span>
            stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>num<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span><span class="token punctuation">)</span>

    console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>stack<span class="token punctuation">)</span>

    <span class="token keyword">return</span> stack<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br></div></div><h4 id="_224-基本计算器"><a href="#_224-基本计算器" class="header-anchor">#</a> 224. 基本计算器</h4> <p>给你一个字符串表达式 <code>s</code> ，请你实现一个基本计算器来计算并返回它的值。</p> <p>注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 <code>eval()</code> 。</p> <p><strong>示例 1：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：s = &quot;1 + 1&quot;
输出：2
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：s = &quot; 2-1 + 2 &quot;
输出：3
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 3：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：s = &quot;(1+(4+5+2)-3)+(6+8)&quot;
输出：23
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>1 &lt;= s.length &lt;= 3 * 105</code></li> <li><code>s</code> 由数字、<code>'+'</code>、<code>'-'</code>、<code>'('</code>、<code>')'</code>、和 <code>' '</code> 组成</li> <li><code>s</code> 表示一个有效的表达式</li> <li>'+' 不能用作一元运算(例如， &quot;+1&quot; 和 <code>&quot;+(2 + 3)&quot;</code> 无效)</li> <li>'-' 可以用作一元运算(即 &quot;-1&quot; 和 <code>&quot;-(2 + 3)&quot;</code> 是有效的)</li> <li>输入中不存在两个连续的操作符</li> <li>每个数字和运行的计算将适合于一个有符号的 32位 整数</li></ul> <h5 id="解题思路-6"><a href="#解题思路-6" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 转换为后缀表达式
   遇到数字，入stack栈（后缀表达式的栈）
   遇到左括号，直接入符号栈
   遇到运算符，如果符号栈栈顶优先级<span class="token operator">&gt;=</span>当前运算符，符号栈出栈，元素    push到stack栈，直到条件不满足，将当前运算符入符号栈
   遇到右括号，出栈符号栈，元素push到stack栈，直到为左括号，左括号也出栈
   把符号栈剩下的元素都push到stack栈中
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><ul><li>注意点
<ul><li>连续数字的处理 parse_nums
<ul><li>第一次数字，parse_nums, val=val*10+currVal</li> <li>直到不是数字</li></ul></li> <li>-号作为数字符号位的处理
<ul><li>例如 -8 转换为0-8</li> <li>需要转换的情况
<ul><li>(  后面的数字</li> <li>+号-号后面的数字</li></ul></li></ul></li></ul></li></ul> <h5 id="完整代码-8"><a href="#完整代码-8" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {string} s
 * @return {number}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">calculate</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">s</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">// 获取优先级</span>
  <span class="token keyword">const</span> <span class="token function-variable function">getRand</span> <span class="token operator">=</span> <span class="token parameter">ch</span> <span class="token operator">=&gt;</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>ch <span class="token operator">===</span> <span class="token string">'+'</span> <span class="token operator">||</span> ch <span class="token operator">===</span> <span class="token string">'-'</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">return</span> <span class="token number">1</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">if</span> <span class="token punctuation">(</span>ch <span class="token operator">===</span> <span class="token string">'('</span> <span class="token operator">||</span> ch <span class="token operator">===</span> <span class="token string">')'</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">return</span> <span class="token number">0</span>
    <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 解题思路</span>

  <span class="token comment">// 将中缀表达式转换为后缀表达式</span>

  <span class="token comment">// 遇到数字，直接输出</span>

  <span class="token comment">// 遇到左括号，直接入栈</span>

  <span class="token comment">// 遇到运算符，如果运算符的优先级&lt;=栈顶 将栈顶出栈，直到条件不满足，将运算符入栈</span>

  <span class="token comment">// 遇到右括号，出栈所有符号，同时输出，出栈左括号</span>

  <span class="token comment">// 处理特殊情况</span>
  <span class="token comment">// need_zero 是否需要前补零 例如(-2+3)*7 ==&gt; (0-2+3)*7</span>
  <span class="token comment">// parse_nums 是否需要进行数字的拼接 (11+22)*3  1拼上1 2要拼上2</span>

  <span class="token keyword">let</span> need_zero <span class="token operator">=</span> <span class="token boolean">true</span>
  <span class="token keyword">let</span> parse_nums <span class="token operator">=</span> <span class="token boolean">false</span>
  <span class="token comment">// 存储后缀表达式</span>
  <span class="token keyword">let</span> stack <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>

  <span class="token comment">// 存储操作符</span>
  <span class="token keyword">let</span> ops <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
  <span class="token comment">// 存储parse的数值</span>
  <span class="token keyword">let</span> val <span class="token operator">=</span> <span class="token number">0</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> s<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">let</span> code <span class="token operator">=</span> s<span class="token punctuation">.</span><span class="token function">charCodeAt</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span>

    <span class="token comment">// 为数字</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>code <span class="token operator">&gt;=</span> <span class="token number">48</span> <span class="token operator">&amp;&amp;</span> code <span class="token operator">&lt;=</span> <span class="token number">57</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      val <span class="token operator">=</span> val <span class="token operator">*</span> <span class="token number">10</span> <span class="token operator">+</span> code <span class="token operator">-</span> <span class="token number">48</span>
      parse_nums <span class="token operator">=</span> <span class="token boolean">true</span>
      <span class="token keyword">continue</span>
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>parse_nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">// 数字后面遇到不是数字的</span>
      parse_nums <span class="token operator">=</span> <span class="token boolean">false</span>
      <span class="token comment">// 不需要补零 (10-2) (10+2)</span>
      need_zero <span class="token operator">=</span> <span class="token boolean">false</span>
      <span class="token comment">// 把parse好的数字入栈</span>
      stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>val<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
      val <span class="token operator">=</span> <span class="token number">0</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 为空格</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">===</span> <span class="token string">' '</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">continue</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 为符号</span>

    <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">===</span> <span class="token string">'('</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      ops<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
      <span class="token comment">// 左括号在数字前面，需要补零（-2+3）==&gt;(0-2+3)</span>
      need_zero <span class="token operator">=</span> <span class="token boolean">true</span>
      <span class="token keyword">continue</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">===</span> <span class="token string">')'</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">// 直接输出，直到左括号</span>

      <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> op <span class="token operator">=</span> ops<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>op <span class="token operator">===</span> <span class="token string">'('</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
          <span class="token comment">// ops.pop()</span>
          <span class="token keyword">break</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
          stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>op<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token punctuation">}</span>
      <span class="token punctuation">}</span>
      <span class="token comment">// 右括号 (xxx)+2 (xxx)-2</span>
      need_zero <span class="token operator">=</span> <span class="token boolean">false</span>
      <span class="token keyword">continue</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 如果是+ - 号</span>

    <span class="token comment">// 走到这里，说明符号是正负号，需要处理补零的</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>need_zero<span class="token punctuation">)</span> <span class="token punctuation">{</span>
      stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token string">'0'</span><span class="token punctuation">)</span>
      <span class="token comment">// need_zero=false</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 判断栈顶和运算符的优先级</span>

    <span class="token comment">// 栈顶大于新来的</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>ops<span class="token punctuation">.</span>length <span class="token operator">&amp;&amp;</span> <span class="token function">getRand</span><span class="token punctuation">(</span>ops<span class="token punctuation">[</span>ops<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">&gt;=</span> <span class="token function">getRand</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> op <span class="token operator">=</span> ops<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
      stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>op<span class="token punctuation">)</span>
    <span class="token punctuation">}</span>

    ops<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
    need_zero <span class="token operator">=</span> <span class="token boolean">true</span> <span class="token comment">// + -号也需要补零 48+-49  18-+48</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 如果parse_nums=true 还在parse</span>
  <span class="token comment">// 直接入栈</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span>parse_nums<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>val<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
  <span class="token punctuation">}</span>

  <span class="token keyword">while</span> <span class="token punctuation">(</span>ops<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>ops<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
  <span class="token punctuation">}</span>

  <span class="token comment">// 得到后缀表达式</span>
  console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>stack<span class="token punctuation">)</span>
<span class="token punctuation">}</span>

<span class="token function">calculate</span><span class="token punctuation">(</span><span class="token string">'(1+(4+5+2)-3)+(6+8)'</span><span class="token punctuation">)</span>

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br><span class="line-number">82</span><br><span class="line-number">83</span><br><span class="line-number">84</span><br><span class="line-number">85</span><br><span class="line-number">86</span><br><span class="line-number">87</span><br><span class="line-number">88</span><br><span class="line-number">89</span><br><span class="line-number">90</span><br><span class="line-number">91</span><br><span class="line-number">92</span><br><span class="line-number">93</span><br><span class="line-number">94</span><br><span class="line-number">95</span><br><span class="line-number">96</span><br><span class="line-number">97</span><br><span class="line-number">98</span><br><span class="line-number">99</span><br><span class="line-number">100</span><br><span class="line-number">101</span><br><span class="line-number">102</span><br><span class="line-number">103</span><br><span class="line-number">104</span><br><span class="line-number">105</span><br><span class="line-number">106</span><br><span class="line-number">107</span><br><span class="line-number">108</span><br><span class="line-number">109</span><br><span class="line-number">110</span><br><span class="line-number">111</span><br><span class="line-number">112</span><br><span class="line-number">113</span><br><span class="line-number">114</span><br><span class="line-number">115</span><br><span class="line-number">116</span><br><span class="line-number">117</span><br><span class="line-number">118</span><br><span class="line-number">119</span><br><span class="line-number">120</span><br><span class="line-number">121</span><br><span class="line-number">122</span><br><span class="line-number">123</span><br><span class="line-number">124</span><br><span class="line-number">125</span><br><span class="line-number">126</span><br><span class="line-number">127</span><br></div></div></div></div>  <div class="page-edit"><div class="edit-link"><a href="https://github.com/linxin1123/vuepress-blog/edit/master/docs/07.算法/41.算法训练营/01.数组-链表-栈-队列-cnblog.md" target="_blank" rel="noopener noreferrer">编辑</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----> <div class="last-updated"><span class="prefix">上次更新:</span> <span class="time">2023/02/17, 11:29:32</span></div></div> <div class="page-nav-wapper"><div class="page-nav-centre-wrap"><a href="/note/js-sf/" class="page-nav-centre page-nav-centre-prev"><div class="tooltip">js数据结构与算法笔记</div></a> <a href="/pages/8585b9/" class="page-nav-centre page-nav-centre-next"><div class="tooltip">数组-链表-栈-队列（下）-cnblog</div></a></div> <div class="page-nav"><p class="inner"><span class="prev">
        ←
        <a href="/note/js-sf/" class="prev">js数据结构与算法笔记</a></span> <span class="next"><a href="/pages/8585b9/">数组-链表-栈-队列（下）-cnblog</a>→
      </span></p></div></div></div> <div class="article-list"><div class="article-title"><a href="/archives/" class="iconfont icon-bi">最近更新</a></div> <div class="article-wrapper"><dl><dd>01</dd> <dt><a href="/pages/0b785d/"><div>
            Vuex
            <!----></div></a> <span class="date">03-14</span></dt></dl><dl><dd>02</dd> <dt><a href="/pages/c59cc0/"><div>
            Vue响应式原理
            <!----></div></a> <span class="date">03-14</span></dt></dl><dl><dd>03</dd> <dt><a href="/pages/83cc7a/"><div>
            Vue虚拟DOM-cnblog
            <!----></div></a> <span class="date">03-14</span></dt></dl> <dl><dd></dd> <dt><a href="/archives/" class="more">更多文章&gt;</a></dt></dl></div></div></main></div> <div class="footer"><div class="icons"><a href="3010733382@qq.com" title="发邮件" target="_blank" class="iconfont icon-youjian"></a><a href="https://github.com/linxin1123" title="GitHub" target="_blank" class="iconfont icon-github"></a><a href="https://music.163.com/#/playlist?id=755597173" title="听音乐" target="_blank" class="iconfont icon-erji"></a></div> 
  Theme by
  <a href="https://github.com/xugaoyi/vuepress-theme-vdoing" target="_blank" title="本站主题">Vdoing</a> 
    | Copyright © 2022-2023
    <span>lingxin | <a href="https://github.com/linxin1123/vuepress-blog/blob/master/LICENSE" target="_blank">MIT License</a></span></div> <div class="buttons"><div title="返回顶部" class="button blur go-to-top iconfont icon-fanhuidingbu" style="display:none;"></div> <div title="去评论" class="button blur go-to-comment iconfont icon-pinglun" style="display:none;"></div> <div title="主题模式" class="button blur theme-mode-but iconfont icon-zhuti"><ul class="select-box" style="display:none;"><li class="iconfont icon-zidong">
          跟随系统
        </li><li class="iconfont icon-rijianmoshi">
          浅色模式
        </li><li class="iconfont icon-yejianmoshi">
          深色模式
        </li><li class="iconfont icon-yuedu">
          阅读模式
        </li></ul></div></div> <!----> <!----> <!----></div><div class="global-ui"><div></div></div></div>
    <script src="/assets/js/app.57550e13.js" defer></script><script src="/assets/js/2.f014c35f.js" defer></script><script src="/assets/js/99.07dc87d8.js" defer></script>
  </body>
</html>
